CodeForces Round 642 Div3 A~F题解

前面四题都比较简单,搞快一点

A:比较显然的的是,n是1的时候答案是0,n是2的时候答案是m,其余的情况观察样例最多是2m

typedef long long ll;

int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
		int n,m;scanf("%d%d",&n,&m);
		if(n == 1)	printf("0\n");
		else if (n == 2)	printf("%d\n",m);
		else printf("%d\n",2 * m);
    }
    return 0;
}

B:开两个堆,一共迭代最多K次,每次从a里面找出最小的,从b里面找出最大的,把两者交换一下,如果发现交换没有价值的时候说明可以提前退出了。

typedef long long ll;

int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
		int n,k,x;scanf("%d%d",&n,&k);
		priority_queue<int,vector<int>,greater<int> >pa;
		priority_queue<int,vector<int>,less<int> > pb;
		for(int i = 1;i <= n;++i)
			scanf("%d",&x),pa.push(x);
		for(int i = 1;i <= n;++i)
			scanf("%d",&x),pb.push(x);
		for(int i = 1;i <= k;++i)
		{
			int ta = pa.top();pa.pop();
			int tb = pb.top();pb.pop();
			if(ta < tb)
			{
				pa.push(tb);
				pb.push(ta);
			}
			else
			{
				pa.push(ta);
				pb.push(tb);
				break;
			}
		}
		int res = 0;
		while(!pa.empty())
		{
			res += pa.top();
			pa.pop();
		}
		printf("%d\n",res);
    }
    return 0;
}

C:可以猜出一个结论,那就是想要所有距离最短,肯定是所有的都最短,那么就是所有的点都往中心走就可以了,题目又刚好说n一定是奇数,于是可以果断猜出结论就是全部往中心走。接着可以发现数字的规律是一圈一圈增大的,中心是0,往外环绕一圈的是1,再往外就是2,因此可以推出规律:对于当前在考虑的数字ii,它一共出现了i/28\lfloor i/2\rfloor * 8次,总数是i/2\lfloor i/2\rfloor个,因此答案就是
res = i=1,ini/28i/2\sum\limits_{i=1,i是奇数}^n\lfloor i/2\rfloor * 8 * \lfloor i/2\rfloor

typedef long long ll;

int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
		ll n;scanf("%lld",&n);
		ll res = 0;
		for(ll i = 1;i <= n;i += 2)
			res += (i / 2) * 8 * (i / 2);
		printf("%lld\n",res);
    }	
    return 0;
}

D:维护一个堆,里面的元素带两个值,第一个是总长度len,第二个是左端点l。每次从堆里面取出len最大的元素,以及l最小的元素,注意:由于第一关键字按最大的排序,因此l在插入的时候是插入的负l,做的时候要转换。

typedef long long ll;
typedef pair<int,int> pii;//len&lp
const int N = 2e5+7;
int res[N];
int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
    	int n;scanf("%d",&n);
		if(n == 1)
		{
			printf("1\n");
			continue;
		}
		priority_queue<pii> pq;
		pq.push({n,-1});
		int i = 1;
		while(!pq.empty())
		{
			pii t = pq.top();pq.pop();
			int len = t.first,l = -t.second;
			int r = l + len - 1;
			int pos = (r - l + 1) % 2 == 1 ? (l + r) / 2 : (l + r - 1) / 2;
			res[pos] = i++;
    		//left
    		if(pos - l > 0)	pq.push({pos - l,-l});
    		//right
    		if(r - pos > 0) pq.push({r - pos,-pos - 1});
    	}
    	for(int i = 1;i <= n;++i)	printf("%d ",res[i]);
    	puts("");
    }
    return 0;
}

E:
题意:给定一个长度为nn的只有01的字符串,和一个数值kk。你可以执行一个操作:选择字符串中的一个数字让他反转,现在要求字符串中每一对1的之间恰好有k1k-1个0,问最少要执行多少次操作。
注意:字符串并不是一个环形的,不要求第一个必须也跟最后一个环上满足,同时你也可以让所有的11变成0,这也是满足题意得。
数据范围:1T250001 \leq T \leq 25000组数据
1n1061 \leq n \leq 10^61kn1 \leq k \leq n
分析:如果我们把原字符串S分成K组,按i...i+k...i+2k...i...i+k...i+2k...分,可以发现,对于一个合法方案来说,一定是只有其中某一组可以存在11,而其他的所有组都不能存在11,必须全部划到00。因此第一步首先分组并求出每一组自身的数值和,数值和等价于让这一组数全部推成00的代价。进而,我们可以枚举每一组数作为能存在11的序列的时候,所需要的总代价,这分为两个部分:一是把其他序列推成00的代价,二是把当前这个序列推成带有一且合法的序列,前面一个部分比较好算,计算所有序列的和再把当前这一组的和挖掉就可以了,对于第二部分,首先一个合法的序列是形如一段连续的00,一段连续的11,一段连续的0这样的序列考虑dp,记fpf_p是当前字符串p中,让末尾的1出现在p位置的最小代价,不难发现dp转移只有两种来源,一是pp位置就是第一个11,这时fp=[0,p1]f_p = \sum[0,p-1],即让前面推成0的代价;二是前面有11,当前的pp是末尾,此时fp=fp1f_p = f_{p - 1},这里要注意的是,如果t[p]t[p]不是11,则需要对之额外增加11的代价。
那么,记res[i]res[i]是把ii组字符串作为存在11序列的代价,可以推出:
res[i]={[0,len1]0min(part[p])res[i]=\begin{cases}\sum[0,len - 1]&最坏情况整个序列推到0\\min(part[p])&一般情况\end{cases}
其中part[p]=fp+[0,len1][p,len1]part[p] = f_p + \sum[0,len - 1] - \sum[p,len - 1] 即末尾p之前的代价和p之后推到0的代价总和,min(part[p])min(part[p])表示在p[0,len1]p∈[0,len-1]中取最小值。
最后,实际的答案rres=min(res[i]+i)rres = min(res[i] + 所有总和 - 当前i的和)
(我的代码实现比较复杂,如果能自己写出来更好)

typedef long long ll;
const int N = 1e6+7;
char s[N];

int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
		int n,k;scanf("%d%d",&n,&k);
		scanf("%s",s);
		int tot = 0;
		for(int i = 0;i < n;++i)	tot += s[i] - '0';
    	vector<string> groups(k);
    	for(int i = 0;i < n;++i)
    		groups[i % k].push_back(s[i]);
    	int res = 1e9+7;
    	for(int j = 0;j < k;++j)
    	{
    		string& s = groups[j];
    		int sz = s.size();
    		int ptot = 0,fres,pref = 0;
    		for(int i = 0;i < sz;++i)	ptot += s[i] - '0';
    		fres = ptot;
    		vector<int> fp(sz,0);
    		for(int i = 0;i < sz;++i)
    		{
    			fp[i] = 1 - int(s[i] == '1');
    			if(i > 0)	fp[i] = min(fp[i - 1],pref) + (s[i] != '1');
    			pref += s[i] == '1';
    			fres = min(fres,fp[i] + ptot - pref);
    		}
    		res = min(res,fres + tot - ptot);
    	}
    	
    	printf("%d\n",res);
    }
    return 0;
}

F:
题意: 有一个nxmnxm的棋盘,棋盘上有一些数字a[i][j]a[i][j],起始时你在(1,1)(1,1)上,你想要移动到(n,m)(n,m)这个位置上,每次移动,你只能从当前位置向右走和向下走,且必须满足目标位置的数字是刚好等于当前位置上的数+1+1的。为了保证你可以从起始位置走到终点,你可以在走之前执行若干次以下这种操作:把某个位置上的数1-1,问你能从起始位置走到终点位置,最少需要的操作是多少次。
注意:你可以修改起始位置的数值,数值也可以修改到负数。
数据范围:T组数据 1T1001 \leq T \leq 100
1n,m1001 \leq n,m \leq 100
1a[i][j]10151 \leq a[i][j] \leq 10^{15}
分析:最少次数,联想到bfs,但是这个题单纯的从起点搜到终点肯定没法对值进行操作,进一步的可以贪心想到可能会有一个作为基准的值:对于某一个修改方案来说,一定至少存在某一个点(x,y)(x,y)的值是没有修改过的,因为假如所有的点都被修改了,那么这个所有数都修改的方案,一定对应着某一个至少有一个数没有修改过的方案(把所有数都+1相当于没加),并且后者的操作次数更少,因此对于某个合法的修改方案来说一定至少有一个没有被修改的值。这启发我们可以枚举每个位置的值作为基准,作为那个前后修改过后不变的值,进而推出所有其他的值。
假设这个棋盘是有(0,0)(0,0)位置的(这么做的原因是相对坐标比较好算,从题目给的那个起始开始算要算一些加一减一的问题),设b[i][j]b[i][j]表示,点(i,j)(i,j)修改到合法方案时的值;点(x,y)(x,y)是当前枚举的那个不动点,则对于不动点来说,有:b[x][y]=a[x][y]=b[0][0]+x+yb[x][y] = a[x][y] = b[0][0] + x + y,因为每次移动的时候都必须是下一个位置值恰好增大11,所以坐标之和就是差,故可以根据这个式子直接推出b[0][0]=b[x][y]xyb[0][0] = b[x][y] - x - y,同时对于其他点,最终要修改到的值也就可以推出来了。
接下来枚举不动点,从每个不动点开始搜bfs就可以了,不过这里要从不动点分别往左上和右下搜索。对于下一个拓展的位置(a,b)(a,b)来说,必须要满足a[a][b]b[x][y]a[a][b] \geq b[x][y],才可以拓展,并且新的路径和就是修改次数,直接加进去就可以,最终答案就是dist[1][1]+dist[n][m]dist[1][1] + dist[n][m]
这里在具体实现上来说,需要使用优先队列bfs,元素是一对坐标值,这里重载了pair<int,int>pair<int,int>的比较器,使之top()top()就是当前dist[x][y]dist[x][y]最小的值。

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define x first
#define y second
const int N = 105;
ll INF = 0x3f3f3f3f3f3f3f3f,res;
ll dist[N][N];

struct cmp
{
	bool operator()(const pii& a,const pii& b)
	{
		return dist[a.x][a.y] > dist[b.x][b.y];
	}
};
ll a[N][N];
int n,m;

void bfs(int sx,int sy)
{
	memset(dist,0x3f,sizeof dist);
	priority_queue<pii,vector<pii>,cmp> pq;
	pq.push({sx,sy});
	dist[sx][sy] = 0;
	ll b = a[sx][sy] - sx - sy;
	while(!pq.empty())
	{
		pii t = pq.top();pq.pop();
		int x = t.x,y = t.y;
		if(x - 1 >= 0 && a[x - 1][y] >= b + x - 1 + y
		&& dist[x - 1][y] > dist[x][y] + a[x - 1][y] - (b + x - 1 + y))
		{
			dist[x - 1][y] = dist[x][y] + a[x - 1][y] - (b + x - 1 + y);
			pq.push({x - 1,y});
		}
		if(y - 1 >= 0 && a[x][y - 1] >= b + x + y - 1
		&& dist[x][y - 1] > dist[x][y] + a[x][y - 1] - (b + x + y - 1))
		{
			dist[x][y - 1] = dist[x][y] + a[x][y - 1] - (b + x + y - 1);
			pq.push({x,y - 1});
		}
	}
	pq.push({sx,sy});
	while(!pq.empty())
	{
		pii t = pq.top();pq.pop();
		int x = t.x,y = t.y;
		if(x + 1 <= n && a[x + 1][y] >= b + x + 1 + y
		&& dist[x + 1][y] > dist[x][y] + a[x + 1][y] - (b + x + 1 + y))
		{
			dist[x + 1][y] = dist[x][y] + a[x + 1][y] - (b + x + 1 + y);
			pq.push({x + 1,y});
		}
		if(y + 1 <= m && a[x][y + 1] >= b + x + y + 1
		&& dist[x][y + 1] > dist[x][y] + a[x][y + 1] - (b + x + y + 1))
		{
			dist[x][y + 1] = dist[x][y] + a[x][y + 1] - (b + x + y + 1);
			pq.push({x,y + 1});
		}
	}
	res = min(res,dist[1][1] + dist[n][m]);
}
int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
		scanf("%d%d",&n,&m);
    	for(int i = 1;i <= n;++i)
    		for(int j = 1;j <= m;++j)
    			scanf("%lld",&a[i][j]);
    	res = INF;
    	for(int i = 1;i <= n;++i)
    		for(int j = 1;j <= m;++j)
    			bfs(i,j);
    	printf("%lld\n",res);
    }
    return 0;
}

DP solution:
这个题目规定的行进路线是从起始点到最右下角,同时只能向右和向下走,这可以联系到一个很简单的DP路径问题:每个点上的权值都是固定的,从某个点走到另一个点,如果合法则增加一个值,如果不合法那么下一步的位置上就是障碍。
因此在上面分析过后,事实上DP解也是比较好想到的,首先也是枚举所有点作为基准的情况,其次每次从(1,1)(1,1)开始往右方向和下方向递推,如果合法就记录当前位置权值+1和下一个点的差值,否则就直接设置成INFINF,最终答案是所有到最终点的最小权值和的最小值。
DP:
状态:f[x][y]f[x][y]表示走到(x,y)(x,y)最小的花费。
入口:初始f[1][1]=b[0][0]+2INFf[1][1] = b[0][0] + 2 其余INF,若起始点无法到达(a[1][1]<b+2a[1][1] < b+2)则直接返回INFINF
出口:minf[n][m]min{f[n][m]}
转移:要注意为横和竖边角单独处理,其余的时候有:
a[x][y]>b+x+ya[x][y] > b + x + y时,当前(x,y)(x,y)是可以到达的,遂更新
dist[x][y]=a[x][y](b+x+y)+min(dist[x1][y],dist[x][y1])dist[x][y] = a[x][y] - (b + x + y) + min(dist[x - 1][y],dist[x][y - 1])

typedef long long ll;
typedef pair<int, int> pii;
#define x first
#define y second
const int N = 105;
ll INF = 0x3f3f3f3f3f3f3f3f, res;
ll dist[N][N];

ll a[N][N];
int n, m;
ll dp(int sx, int sy)
{
    memset(dist, 0x3f, sizeof dist);
    ll b = a[sx][sy] - sx - sy;
    if(a[1][1] < b + 2)	return INF;
    dist[1][1] = a[1][1] - (b + 2);
    for(int i = 2;i <= m;++i)	
    	if(a[1][i] >= b + 1 + i)
    		dist[1][i] = a[1][i] - (b + 1 + i) + dist[1][i - 1];
    for(int i = 2;i <= n;++i)
    	if(a[i][1] >= b + i + 1)
    		dist[i][1] = a[i][1] - (b + i + 1) + dist[i - 1][1];
    for (int i = 2; i <= n; ++i)
        for (int j = 2; j <= m; ++j)
            if (a[i][j] >= b + i + j)
                dist[i][j] = a[i][j] - (b + i + j) + min(dist[i - 1][j],dist[i][j - 1]);
    return dist[n][m];
}
int main()
{
    int T; scanf("%d", &T);
    while (T--)
    {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= m; ++j)
                scanf("%lld", &a[i][j]);
        res = INF;
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= m; ++j)
                res = min(dp(i, j), res);
        printf("%lld\n", res);
    }
    return 0;
}

此外,上面的代码是使用的(x,y)(x,y)有哪些状态组成,如果写成出边转移的方式的话会更简单一些,不需要像上面那样写特殊处理

ll dp(int sx, int sy)
{
    memset(dist, 0x3f, sizeof dist);
    ll b = a[sx][sy] - sx - sy;
    if(a[1][1] < b + 2)	return INF;
    dist[1][1] = a[1][1] - (b + 2);
    for(int i = 1;i <= n;++i)
        for(int j = 1;j <= m;++j)
        {
            if(i + 1 <= n && a[i + 1][j] >= b + i + 1 + j)
                dist[i + 1][j] = min(dist[i + 1][j],a[i + 1][j] - (b + i + 1 + j) + dist[i][j]);
            if(j + 1 <= m && a[i][j + 1] >= b + i + j + 1)
                dist[i][j + 1] = min(dist[i][j + 1],a[i][j + 1] - (b + i + j + 1) + dist[i][j]);
        }
    return dist[n][m];
}